package com.test.pack1.demo.base1_5;

/**
 * Created by dws on 2017/11/30.
 *
 * 原理是将连线点转化为同一个数字,然后再判断该点上的数字是否相等
 */
public class UF implements UnionInterface {

    private int[][] test;

    private int[] id;//分量id
    private int count; //分量数量

    public UF(int N) {//初始化分量id数据
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++) {
            id[i]=i;
        }
    }

    @Override
    public void union(int p, int q) {
        int pID = find(p);
        int qID = find(q);
        if(pID==qID)return;

        for (int i = 0; i < id.length; i++) {
            if(id[i]==pID)id[i]=qID;
        }
        count--;
    }

    @Override
    public int find(int p) {
        return id[p];
    }

    @Override
    public boolean connected(int p, int q) {
        return find(p)==find(p);
    }

    @Override
    public int count() {
        return count;
    }

    public static void main(String[] args) {
        UF uf = new UF(10);
       /* uf.test = new int[11][2];
        uf.test[0]=new int[]{4,3};
        uf.test[1] = new int[]{3,8};*/
        uf.test = new int[][]{new int[]{4,3},
            new int[]{3,8},new int[]{6,5},new int[]{9,4},
            new int[]{2,1},new int[]{8,9},new int[]{5,0},
            new int[]{7,2},new int[]{6,1},new int[]{1,0},
            new int[]{6,7}
        };
        for (int i = 0; i < uf.test.length; i++) {
            uf.union(uf.test[i][0],uf.test[i][1]);
        }
        toStr(uf.id);
        System.out.println(uf.connected(7,8));
        toStr(uf.id);
    }

    public static  void toStr(int[] obj){
        for (int i = 0; i < obj.length; i++) {
            System.out.print(obj[i]);
        }
        System.out.println();
    }


}
